Since relation and its fragments in the distributed database have multiple copies and multi-site storage characteristics, which increases the time and space complexity of query and results in lower search efficiency of Query Execution Plan (QEP), a Parallel Genetic Algorithm and Max-Min Ant System (PGA-MMAS) based on design principles of Fragments Site Selector (FSS) was proposed. Firstly, based on the design requirement of the distributed information management system for actual business, FSS was designed, which selected the best one from many copies of relationship heuristically to decrease query join cost and search space of PGA-MMAS. Secondly, Genetic Algorithm (GA) encoded the final join relations and conducted parallel genetic operation to get a set of relative optimal QEPs by taking advantage of quick convergence of GA. Then, QEPs were transformed into the initial pheromone distribution of Max-Min Ant System (MMAS) to obtain the optimal QEP quickly and efficiently. Finally, simulation experiments were conducted under different number of relation conditions, and the results show that PGA-MMAS based on FSS searches optimal QEP more efficiently than original GA, Fragments Site Selector-Genetic Algorithm (FSS-GA), Fragments Site Selector-Max-Min Ant System (FSS-MMAS) and Fragments Site Selector-Genetic Algorithm-Max-Min Ant System (FSS-GA-MMAS). And in the actual engineering application, the proposed algorithm can search high-quality QEP to improve the efficiency of multi-join query in distributed database.